/******************************************************************************************
 *****                              File Description Table                              ***
 ******************************************************************************************
 *                                                                                        *
 *               File Name          :   SequenceList.c                                    *
 *                                                                                        *
 *               Author             :   cxm                                               *
 *                                                                                        *
 *               Creation Date      :   2025/03/17                                        *
 *                                                                                        *
 *               Last Modifief Date :   2025/03/17                                        *
 *                                                                                        *
 *----------------------------------------------------------------------------------------*
 * Description: 
 * 1. 顺序表操作  
 *========================================================================================*/                                                                                
/******************************************************************************************
*                                 头 文 件 引 用                             
*========================================================================================*/
#include "SequenceList.h"

#include <stdio.h>       
#include <string.h>                                                            
                                       
/******************************************************************************************
*                                 全 局 变 量 声 明                            
*========================================================================================*/
/** 
 * @brief: 全局顺序表定义
 * 
 */
SqList gst_sqlist = {0};                                                                   
                          
/******************************************************************************************
*                                 对 外 函 数 接 口 声 明                         
*========================================================================================*/
BOOL SqList_Init(SqList *pst_List, INT16U ush_MaxLen);          
BOOL SqList_DeInit(SqList *pst_List);  

BOOL Sqlist_Add(SqList *pst_List, INT16S sh_Val);
BOOL SqList_Insert(SqList *pst_List, INT16U ush_Idx,INT16S sh_Val);
BOOL SqList_Delete(SqList *pst_List, INT16U ush_Idx, INT16S *psh_Val);
BOOL SqList_SearchByIdx(SqList *pst_List, INT16U ush_Idx, INT16S *psh_Val);
BOOL SqList_SearchByVal(SqList *pst_List, INT16U *push_Idx, INT16S sh_Val);
BOOL SqList_SearchMaxVal(SqList *pst_List, INT16S *psh_Val);
BOOL SqList_SearchMinVal(SqList *pst_List, INT16S *psh_Val);
BOOL SqList_Merge(SqList *pst_List, SqList *pst_List1, SqList *pst_List2);
BOOL SqList_Clean(SqList *pst_List);
BOOL SqList_IsEmpty(SqList *pst_List);

BOOL SqList_BubbleSort(SqList *pst_List);
BOOL SqList_Print(SqList *pst_List);                       
                                                       
/******************************************************************************************
*                                 对 外 函 数 接 口 实 现                          
*========================================================================================*/
/** 
 * @brief: 顺序表 初始化
 * 
 * @param: 
 *      [in] pst_List   : 顺序表
 *      [in] ush_MaxLen : 最大长度
 * 
 * @return: 
 *      [out] TRUE  : 初始化成功
 *      [out] FALSE : 初始化失败
 */
BOOL SqList_Init(SqList *pst_List, INT16U ush_MaxLen)
{
    if(pst_List == NULL) 
    {
        return FALSE;
    }

    pst_List->ush_Len = 0;
    pst_List->ush_MaxLen = ush_MaxLen;
    pst_List->psh_Base = (INT16S *)malloc(sizeof(INT16S) * ush_MaxLen);

    if(pst_List->psh_Base == NULL)
    {
        pst_List->ush_MaxLen = 0;
        return FALSE;
    }

    memset(pst_List->psh_Base, 0, sizeof(INT16S) * ush_MaxLen);

    return TRUE;
}      

/** 
 * @brief: 顺序表 销毁
 * 
 * @param: 
 *      [in] pst_List: 顺序表
 * 
 * @return: 
 *      [out] TRUE  : 销毁成功
 *      [out] FALSE : 销毁失败
 */
BOOL SqList_DeInit(SqList *pst_List)
{
    if(pst_List == NULL)
    {
        return FALSE;
    }

    pst_List->ush_Len = 0;
    pst_List->ush_MaxLen = 0;

    if(pst_List->psh_Base != NULL)
    {
        free(pst_List->psh_Base);
        pst_List->psh_Base = NULL;
    }

    return TRUE;
}

/** 
 * @brief: 添加数值到顺序表末尾
 * 
 * @param: 
 *      [in] pst_List: 顺序表
 *      [in] sh_Val  : 待添加数值
 * 
 * @return: 
 *      [out] TRUE  : 添加成功
 *      [out] FALSE : 添加失败
 */
BOOL Sqlist_Add(SqList *pst_List, INT16S sh_Val)
{
    if(pst_List == NULL || pst_List->ush_Len == pst_List->ush_MaxLen)
    {
        return FALSE;
    }

    pst_List->psh_Base[pst_List->ush_Len++] = sh_Val;

    return TRUE;
}

/** 
 * @brief: 删除顺序表中指定位置的数值并返回
 * 
 * @param: 
 *      [in] pst_List       : 顺序表
 *      [in] ush_Idx        : 指定位置
 *      [in][out] psh_Val   : 返回的数值
 * 
 * @return: 
 *      [out] TRUE  : 删除成功
 *      [out] FALSE : 删除失败
 */
BOOL SqList_Delete(SqList *pst_List, INT16U ush_Idx, INT16S *psh_Val)
{
    if(pst_List == NULL || ush_Idx >= pst_List->ush_Len)
    {
        return FALSE;
    }

    *psh_Val = pst_List->psh_Base[ush_Idx];

    for(int i = ush_Idx; i < pst_List->ush_Len; i++)
    {
        pst_List->psh_Base[i] = pst_List->psh_Base[i + 1];
    }

    return TRUE;
}

/** 
 * @brief: 在顺序表的指定位置插入数值
 * 
 * @param: 
 *      [in] pst_List       : 顺序表
 *      [in] ush_Idx        : 指定位置
 *      [in][out] psh_Val   : 插入的数值
 * 
 * @return: 
 *      [out] TRUE  : 插入成功
 *      [out] FALSE : 插入失败
 */
BOOL SqList_Insert(SqList *pst_List, INT16U ush_Idx, INT16S sh_Val)
{
    if(pst_List == NULL || ush_Idx >= pst_List->ush_MaxLen)
    {
        return FALSE;
    }

    for(int i = pst_List->ush_Len; i > 0; i--)
    {
        pst_List->psh_Base[i] = pst_List->psh_Base[i - 1];
    }
    
    pst_List->psh_Base[ush_Idx] = sh_Val;
    ++pst_List->ush_Len;

    return TRUE;
}

/** 
 * @brief: 返回顺序表中指定位置的数值
 * 
 * @param: 
 *      [in] pst_List       : 顺序表
 *      [in] ush_Idx        : 指定位置
 *      [in][out] psh_Val   : 返回的数值
 * 
 * @return: 
 *      [out] TRUE  : 查找成功
 *      [out] FALSE : 查找失败
 */
BOOL SqList_SearchByIdx(SqList *pst_List, INT16U ush_Idx, INT16S *psh_Val)
{
    if(pst_List == NULL || ush_Idx >= pst_List->ush_Len)
    {
        return FALSE;
    }

    psh_Val = pst_List->psh_Base[ush_Idx];

    return TRUE;
}

/** 
 * @brief: 查找某个元素在顺序表中第一次出现的位置
 * 
 * @param: 
 *      [in] pst_List       : 顺序表
 *      [in] push_Idx       : 查找到的位置
 *      [in][out] sh_Val    : 指定数值的数值
 * 
 * @return: 
 *      [out] TRUE  : 查找成功
 *      [out] FALSE : 查找失败
 */
BOOL SqList_SearchByVal(SqList *pst_List, INT16U *push_Idx, INT16S sh_Val)
{
    if(pst_List == NULL)
    {
        return FALSE;
    }

    for(int i = 0; i < pst_List->ush_Len; i++)
    {
        if(pst_List->psh_Base[i] == sh_Val)
        {
            *push_Idx = i;
            return TRUE;
        }
    }

    return FALSE;
}

/** 
 * @brief: 查找顺序表中的最大值
 * 
 * @param: 
 *      [in] pst_List       : 顺序表
 *      [in][out] psh_Val   : 返回的数值
 * 
 * @return: 
 *      [out] TRUE  : 查找成功
 *      [out] FALSE : 查找失败
 */
BOOL SqList_SearchMaxVal(SqList *pst_List, INT16S *psh_Val)
{
    if(pst_List == NULL)
    {
        return FALSE;
    }

    INT16S sh_Max = -32767;

    for(int i = 0; i < pst_List->ush_Len; i++)
    {
        if(pst_List->psh_Base[i] > sh_Max)
        {
            sh_Max = pst_List->psh_Base[i];
        }
    }
    *psh_Val = sh_Max;

    return TRUE;
}

/** 
 * @brief: 查找顺序表中的最小值
 * 
 * @param: 
 *      [in] pst_List       : 顺序表
 *      [in][out] psh_Val   : 返回的数值
 * 
 * @return: 
 *      [out] TRUE  : 查找成功
 *      [out] FALSE : 查找失败
 */
BOOL SqList_SearchMinVal(SqList *pst_List, INT16S *psh_Val)
{
    if(pst_List == NULL)
    {
        return FALSE;
    }

    INT16S sh_Min = 0x7FFF;

    for(int i = 0; i < pst_List->ush_Len; i++)
    {
        if(pst_List->psh_Base[i] < sh_Min)
        {
            sh_Min = pst_List->psh_Base[i];
        }
    }
    *psh_Val = sh_Min;

    return TRUE;
}

/** 
 * @brief: 顺序表 是否为空
 * 
 * @param: 
 *      [in] pst_List: 顺序表
 * 
 * @return: 
 *      [out] TRUE  : 顺序表为空
 *      [out] FALSE : 顺序表不为空
 */
BOOL SqList_IsEmpty(SqList *pst_List)
{
    if(pst_List == NULL || pst_List->ush_Len == 0)
    {
        return TRUE;
    }

    return FALSE;
}

/** 
 * @brief: 合并两个顺序表
 * 
 * @param: 
 *      [in] pst_List    : 合并的顺序表
 *      [in] pst_List1   ：待合并的顺序表1
 *      [in] pst_List2   ：待合并的顺序表2
 * 
 * @return: 
 *      [out] TRUE  : 合并成功
 *      [out] FALSE : 合并失败
 *
 */
BOOL SqList_Merge(SqList *pst_List, SqList *pst_List1, SqList *pst_List2)
{
    if(pst_List1 == NULL && pst_List2 == NULL)
    {
        return FALSE;
    }

    for(int i = 0; i < pst_List1->ush_Len - 1; i++)
    {
        if(pst_List1->psh_Base[i] > pst_List1->psh_Base[i + 1])
        {
            return FALSE;
        }
    }

    for(int i = 0; i < pst_List2->ush_Len - 1; i++)
    {
        if(pst_List2->psh_Base[i] > pst_List2->psh_Base[i + 1])
        {
            return FALSE;
        }
    }

    if(pst_List == NULL)
    {
        pst_List = (SqList *)malloc(sizeof(SqList));
        if(pst_List == NULL || (INT32U)pst_List1->ush_Len + (INT32U)pst_List2->ush_Len > 0x7FFF)
        {
            return FALSE;
        }

        pst_List->psh_Base = (INT16S *)malloc(sizeof(INT16S) * (pst_List1->ush_Len + pst_List2->ush_Len));
        if(pst_List->psh_Base == NULL)
        {
            return FALSE;
        }
        pst_List->ush_Len = 0;
        pst_List->ush_MaxLen = pst_List1->ush_Len + pst_List2->ush_Len;
    }

    INT16U i = 0, j = 0, k = 0;
    while(i < pst_List1->ush_Len && j < pst_List2->ush_Len)
    {
        if(pst_List1->psh_Base[i] < pst_List2->psh_Base[j])
        {
            pst_List->psh_Base[k++] = pst_List1->psh_Base[i++];
        }
        else
        {
            pst_List->psh_Base[k++] = pst_List1->psh_Base[j++];
        }
    }

    while(i < pst_List1->ush_Len)
    {
        pst_List->psh_Base[k++] = pst_List1->psh_Base[i++];
    }

    while (j < pst_List2->ush_Len)
    {
        pst_List->psh_Base[k++] = pst_List1->psh_Base[j++];
    }
    
    return TRUE;
}

/** 
 * @brief: 顺序表 清空
 * 
 * @param: 
 *      [in] pst_List: 顺序表
 * 
 * @return: 
 *      [out] TRUE  : 清空成功
 *      [out] FALSE : 清空失败
 */
BOOL SqList_Clean(SqList *pst_List)
{
    if(pst_List == NULL)
    {
        return FALSE;
    }

    pst_List->ush_Len = 0;
    memset(pst_List->psh_Base, 0, sizeof(INT16S) * pst_List->ush_MaxLen);

    return TRUE;
}

/** 
 * @brief: 顺序表 冒泡排序（从小到大排序）
 * 
 * @param: 
 *      [in] pst_List: 顺序表
 * 
 * @return: 
 *      [out] TRUE  : 排序成功
 *      [out] FALSE : 排序失败
 */
BOOL SqList_BubbleSort(SqList *pst_List)
{
    if(pst_List == NULL || SqList_IsEmpty(pst_List))
    {
        return FALSE;
    }

    INT16S sh_Tmp = 0;

    for(int i = 0; i < pst_List->ush_Len - 1; i++)
    {
        for(int j = pst_List->ush_Len - 1; j > i; j--)
        {
            if(pst_List->psh_Base[j] < pst_List->psh_Base[j - 1])
            {
                sh_Tmp = pst_List->psh_Base[j];
                pst_List->psh_Base[j] = pst_List->psh_Base[j - 1];
                pst_List->psh_Base[j - 1] = sh_Tmp; 
            }
        }
    }

    return TRUE;
}

/** 
 * @brief: 顺序表 打印
 * 
 * @param: 
 *      [in] pst_List: 顺序表
 * 
 * @return: 
 *      [out] TRUE  : 成功
 *      [out] FALSE : 失败
 */
BOOL SqList_Print(SqList *pst_List)
{
    if(pst_List == NULL)
    {
        return FALSE;
    }

    if(SqList_IsEmpty(pst_List))
    {
        printf("顺序表为空\r\n");
    }

    printf("顺序表内容为: ");
    for(int i = 0; i < pst_List->ush_Len; i++)
    {
        printf("%d  ", pst_List->psh_Base[i]);
    }
    printf("\r\n");

    return TRUE;
}
                                                       
  